/**
    @Author         :   Yehuda Roth
     Create Date    :   18/06/2010
     Last Modified  :   26/06/2010
    @Brief          :   Generic Priority Queue, holds pointers to void. Based on static array and rearangement function.
                        U_Test is activated if defines PQ_UTEST.
*/

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#include "PQ.h"

typedef int (*CmpFunc)(void* ,void*);

struct _PQ_
{
    void**                          data;
    int                             head;
    int                             tail;
    int                             size;
    CmpFunc                         cmpFun;             /*  Compare function to rearangement    */
    int                             n_items;
};


PQ* PQCreate(int _size, CmpFunc _cmpFunc)
{
    PQ* pq = 0;

    assert(_size);
    assert(_cmpFunc);

    pq = (PQ*)malloc(sizeof(PQ));
    pq->data = malloc(_size*sizeof(void*));             /*  Array of pointers to items          */
    pq->size = _size;
    pq->n_items = 0;
    pq->cmpFun = _cmpFunc;
    pq->head = 0;
    pq->tail =0;

    return pq;
}

void* PQTop(PQ* _pq)
{
    assert(_pq);

    if(!_pq->n_items)
    {
        return 0;
    }
    return *(_pq->data);                                /*  Return the first item => top        */
}

int PQRearrange(PQ* _pq)
{
    void**    pArr    = 0 ;
    void**    pInSort     ;
    void*     temp        ;
    int       i           ;

    assert(_pq);

    pArr    = _pq->data;
    /*  INSERTION SORT      */
    for(i = 1;i < _pq->n_items ; ++i)
    {
        temp = *(pArr + i);                     /*      From second place and on        */
        pInSort = pArr + i - 1;                 /*      Inner sort from the previous    */

        while(pInSort>= pArr)                   /*      while the pointer on the array  */
        {
            if(_pq->cmpFun(temp, *pInSort) > 0 )    /*  If temp smaller than *pInSort   */
            {
                *(pInSort + 1) = *pInSort;      /*      swap                            */
                *pInSort = temp;
                --pInSort;                      /*      go backwards                    */
            }
            else
            {
                break;
            }
        }
    }

    return 0;
}


int PQInsert(PQ* _pq, void* _item)
{
    assert(_pq);

    *(_pq->data + _pq->n_items) = _item;
    ++_pq->n_items;

    return 0;
}

int PQPushBack(PQ* _pq, void* _item)
{
    assert(_pq);

    PQInsert(_pq, _item);                           /*  Insert at end   */
    PQRearrange(_pq);                               /*  Rearrange       */

    return 0;
}

int PQPop(PQ* _pq, void** OUT _item)
{
    int i;

    assert(_pq);

    if(_pq->n_items == 0)                           /*  Empty Q         */
    {
        return 1;
    }

    *_item = *(_pq->data);
    for(i = 1; i < _pq->n_items ;++i)
    {
        *(_pq->data + i-1) = *(_pq->data + i);
    }
    --_pq->n_items;

    return 0;
}

void PQDestroy(PQ* _pq)
{
    assert(_pq);
    free(_pq->data);
    free(_pq);
}

/***********************************************************************************************************/
/**************************************     PQ_UTEST        ************************************************/
/***********************************************************************************************************/
#ifdef PQ_UTEST

#define IS_SUCCESS(X) !X?"SUCCESS":"FAILURE"   /*  Macro to print on regression tests       */
/***Forward Decleration***/
int PQRegresion_Utest();
int PQPushBack_Utest();
int PQPop_Utest();
/*************************/

int CmpTest(void* a, void* b)
{
    double* aa = (double*)a;
    double* bb = (double*)b;

    return (*aa - *bb);
}

int main()
{
    PQRegresion_Utest();

    return 0;
}

int PQRegresion_Utest()
{
    printf("\nPQPushBack_Utest: %s\n\n",IS_SUCCESS(PQPushBack_Utest()));
    printf("\nPQPop_Utest: %s\n",IS_SUCCESS(PQPop_Utest()));

    return 0;
}

int PQPushBack_Utest()
{
    PQ* pq;
    double* ip1 = malloc(sizeof(double));
    double* ip2 = malloc(sizeof(double));
    double* ip3 = malloc(sizeof(double));
    int size = 4;

    pq = PQCreate(size, CmpTest);

    *ip1 = 10.7888888;
    *ip2 = 6.43545434;
    *ip3 = 4.43545434;
    printf("The entering numbers in this order: %f , %f, %f\n",*ip1,*ip2,*ip3);
    PQPushBack(pq, ip1);
    PQPushBack(pq, ip2);
    PQPushBack(pq, ip3);
    printf("The order in array: pq->data: %f , pq->data+1: %f, pq->data+2: %f\n",**(double**)(pq->data),**(double**)(pq->data + 1),**(double**)(pq->data+2));

    if(**(double**)(pq->data) != *ip3 || **(double**)(pq->data+1) != *ip2 || **(double**)(pq->data+2) != *ip1)
    {   return 1;   }

    return 0;
}

int PQPop_Utest()
{
    PQ*     pq                              ;
    double* ip1     = malloc(sizeof(double));
    double* ip2     = malloc(sizeof(double));
    double* ip3     = malloc(sizeof(double));
    double* dp1                             ;
    double* dp2                             ;
    double* dp3                             ;
    int     size    = 4                     ;

    pq = PQCreate(size, CmpTest);
    *ip1 = 10.7888888;
    *ip2 = 6.43545434;
    *ip3 = 4.43545434;

    printf("The entering numbers in this order: %f , %f, %f\n",*ip1,*ip2,*ip3);
    PQPushBack(pq, ip1);
    PQPushBack(pq, ip2);
    PQPushBack(pq, ip3);

    PQPop(pq, (void**)&dp1);
    PQPop(pq, (void**)&dp2);
    PQPop(pq, (void**)&dp3);
    printf("The popped numbers in this order: %f , %f, %f\n",*dp1,*dp2,*dp3);
    if(dp1 != ip3 || dp2 != ip2 || dp3 != ip1)
    {   return 1;   }

    if(!PQPop(pq, (void**)&ip1))
    { return 1; }

    return 0;
}

#endif      /*  PQ_UTEST    */
